package Tree;

import java.util.Arrays;
import java.util.LinkedList;

public class TreeNode implements TreeInterface{
    private TreeNode left;
    private int val;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }


    @Override
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);

    }

    @Override
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    @Override
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");

    }

    public int count = 0;
    @Override
    public void size(TreeNode node) {
        if (node == null) {
            return;
        }
        count++;
        size(node.left);
        size(node.right);

    }

    @Override
    public int size2(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = size2(node.left);
        int r = size2(node.right);
        return l + r + 1;
    }

    public int getLeafNode = 0;
    @Override
    public void getLeafNodeCount1(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            getLeafNode++;
        }
        getLeafNodeCount1(node.left);
        getLeafNodeCount1(node.right);
    }

    @Override
    public int getLeafNodeCount2(TreeNode node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        int l = getLeafNodeCount2(node.left);
        int r = getLeafNodeCount2(node.right);

        return l + r;
    }

    @Override
    public int getKLevelNodeCount(TreeNode node, int k) {
        if (node == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        int l = getKLevelNodeCount(node.left,k - 1);
        int r = getKLevelNodeCount(node.right,k - 1);
        return l + r;
    }

    @Override
    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = getHeight(node.left);
        int r = getHeight(node.right);
        return Math.max(l,r) + 1;
    }

    @Override
    public TreeNode find(TreeNode node, int value) {
        if (node == null) {
            return null;
        }
        if (node.val == value) {
            return node;
        }
        TreeNode l = find(node.left,value);
        if (l != null) {
            return l;
        }
        TreeNode r = find(node.right,value);
        if (r != null) {
            return r;
        }

        return null;
    }

    @Override
    public void levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while ( !queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
            System.out.print(poll.val + " ");
        }
        System.out.println();

    }

    @Override
    public boolean isCompleteTree(TreeNode node, int depth, int leve) {
        if(node == null) {
            return true;
        }

        if (depth == leve) {
            return node.left == null && node.right == null;
        }

        if (node.left == null || node.right == null) {
            return false;
        }

        return isCompleteTree(node.left,depth,leve + 1) && isCompleteTree(node.right,depth,leve + 1);
    }


    //根据前序与中序来构造二叉树
    public TreeNode prevAndInOrderConstructTree(int[] prevOrder, int[] inOrder) {
        if (prevOrder.length == 0) {
            return null;
        }
        int rootValue = prevOrder[0];
        TreeNode root = new TreeNode(rootValue);
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,i);
                int[] inRight = Arrays.copyOfRange(inOrder,i+1,inOrder.length);

                int[] prevLeft = Arrays.copyOfRange(prevOrder,1,i + 1);
                int[] prevRight = Arrays.copyOfRange(prevOrder,i+1,inOrder.length);

                root.left = prevAndInOrderConstructTree(prevLeft,inLeft);
                root.right = prevAndInOrderConstructTree(prevRight,inRight);
            }
        }
        return root;
    }

    //根据中序与后序来构造二叉树
    public TreeNode inAndPostConstructTree(int[] inOrder, int[] postOrder) {

        if (inOrder.length == 0) {
            return null;
        }
        int rootValue = postOrder[postOrder.length-1];
        TreeNode root = new TreeNode(rootValue);
        for (int j = 0; j < inOrder.length; j++) {
            if (rootValue == inOrder[j]) {
                int[] inLeft = Arrays.copyOfRange(inOrder,0,j);
                int[] inRight = Arrays.copyOfRange(inOrder,j+1,inOrder.length);

                int[] postLeft = Arrays.copyOfRange(postOrder,0,j);
                int[] postRight = Arrays.copyOfRange(postOrder,j,postOrder.length-1);

                root.left = inAndPostConstructTree(inLeft,postLeft);
                root.right = inAndPostConstructTree(inRight,postRight);
            }
        }
        return root;

    }

    //根据后缀表达式创建二叉树
    public TreeNode suffixCreateTree(String s) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            switch (ch) {
                case '+','-','*','/' -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode t = new TreeNode(ch);
                    t.right = right;
                    t.left = left;
                    stack.push(t);
                }
                default -> {
                    stack.push(new TreeNode(ch));
                }
            }

        }
        return stack.peek();
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }

}
